0467. 环绕字符串中唯一的子字符串【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - DP

1. 📝 题目描述

• leetcode

定义字符串 base 为一个 "abcdefghijklmnopqrstuvwxyz" 无限环绕的字符串，所以 base 看起来是这样的：

• "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".

给你一个字符串 s，请你统计并返回 s 中有多少 不同 非空子串 也在 base 中出现。

示例 1：

输入：s = "a"
输出：1
解释：字符串 s 的子字符串 "a" 在 base 中出现。

示例 2：

输入：s = "cac"
输出：2
解释：字符串 s 有两个子字符串 ("a", "c") 在 base 中出现。

示例 3：

输入：s = "zab"
输出：6
解释：字符串 s 有六个子字符串 ("z", "a", "b", "za", "ab", and "zab") 在 base 中出现。

---

提示：

• 1 <= s.length <= 10^5
• s 由小写英文字母组成

2. 🎯 s.1 - DP

c

int findSubstringInWraproundString(char* s) {
    int maxLen[26] = {0};
    int len = 1, n = strlen(s);
    for (int i = 0; i < n; i++) {
        if (i > 0 && (s[i] - s[i - 1] + 26) % 26 == 1) len++;
        else len = 1;
        int idx = s[i] - 'a';
        if (len > maxLen[idx]) maxLen[idx] = len;
    }
    int res = 0;
    for (int i = 0; i < 26; i++) res += maxLen[i];
    return res;
}

js

/**
 * @param {string} s
 * @return {number}
 */
var findSubstringInWraproundString = function (s) {
  const maxLen = new Array(26).fill(0)
  let len = 1
  for (let i = 0; i < s.length; i++) {
    if (i > 0 && (s.charCodeAt(i) - s.charCodeAt(i - 1) + 26) % 26 === 1) {
      len++
    } else {
      len = 1
    }
    const idx = s.charCodeAt(i) - 97
    maxLen[idx] = Math.max(maxLen[idx], len)
  }
  return maxLen.reduce((a, b) => a + b, 0)
}

py

class Solution:
    def findSubstringInWraproundString(self, s: str) -> int:
        max_len = [0] * 26
        length = 1
        for i in range(len(s)):
            if i > 0 and (ord(s[i]) - ord(s[i - 1])) % 26 == 1:
                length += 1
            else:
                length = 1
            idx = ord(s[i]) - 97
            max_len[idx] = max(max_len[idx], length)
        return sum(max_len)

• 时间复杂度：$O(n)$
• 空间复杂度：$O(|\mathrm{\Sigma }|)$

算法思路：

• 记录以每个字符结尾的最长连续环绕子串长度
• 以字符 $c$ 结尾的最长连续子串长度为 $k$，则贡献 $k$ 个不同子串
• 求和即为答案